#include <bits/stdc++.h>
using namespace std;

/*
3003. 执行操作后的最大分割数量
已解答
困难
相关标签
premium lock icon
相关企业
提示
给你一个下标从 0 开始的字符串 s 和一个整数 k。

你需要执行以下分割操作，直到字符串 s 变为 空：

选择 s 的最长 前缀，该前缀最多包含 k 个 不同 字符。
删除 这个前缀，并将分割数量加一。如果有剩余字符，它们在 s 中保持原来的顺序。
执行操作之 前 ，你可以将 s 中 至多一处 下标的对应字符更改为另一个小写英文字母。

在最优选择情形下改变至多一处下标对应字符后，用整数表示并返回操作结束时得到的 最大 分割数量。

 

示例 1：

输入：s = "accca", k = 2

输出：3

解释：

最好的方式是把 s[2] 变为除了 a 和 c 之外的东西，比如 b。然后它变成了 "acbca"。

然后我们执行以下操作：

最多包含 2 个不同字符的最长前缀是 "ac"，我们删除它然后 s 变为 "bca"。
现在最多包含 2 个不同字符的最长前缀是 "bc"，所以我们删除它然后 s 变为 "a"。
最后，我们删除 "a" 并且 s 变成空串，所以该过程结束。
进行操作时，字符串被分成 3 个部分，所以答案是 3。

示例 2：

输入：s = "aabaab", k = 3

输出：1

解释：

一开始 s 包含 2 个不同的字符，所以无论我们改变哪个， 它最多包含 3 个不同字符，因此最多包含 3 个不同字符的最长前缀始终是所有字符，因此答案是 1。

示例 3：

输入：s = "xxyz", k = 1

输出：4

解释：

最好的方式是将 s[0] 或 s[1] 变为 s 中字符以外的东西，例如将 s[0] 变为 w。

然后 s 变为 "wxyz"，包含 4 个不同的字符，所以当 k 为 1，它将分为 4 个部分。

 

提示：

1 <= s.length <= 104
s 只包含小写英文字母。
1 <= k <= 26
*/

// 法一
class Solution {
public:
    int maxPartitionsAfterOperations(string s, int k) {
        int n = s.length();
        // left[i] 存储 [0..i-1] 区间的分割信息:
        // left[i][0] = 分割数, left[i][1] = 最后一块的字符掩码, left[i][2] = 最后一块的不同字符数
        vector<vector<int>> left(n, vector<int>(3));
        // right[i] 存储 [i+1..n-1] 区间的分割信息:
        // right[i][0] = 分割数, right[i][1] = 第一块的字符掩码, right[i][2] = 第一块的不同字符数
        vector<vector<int>> right(n, vector<int>(3));
        
        // 计算左半部分信息 (从左到右遍历)
        int num = 0;       // 已分割的块数
        int mask = 0;      // 当前块的字符掩码 (用位表示存在的字符)
        int count = 0;     // 当前块的不同字符数
        for (int i = 0; i < n - 1; i++) {
            int binary = 1 << (s[i] - 'a');  // 当前字符的位表示
            if (!(mask & binary)) {          // 当前块不含该字符
                count++;
                if (count <= k) {            // 未超过k个不同字符, 加入当前块
                    mask |= binary;
                } else {                     // 超过k个, 分割出当前块
                    num++;
                    mask = binary;           // 新块起始
                    count = 1;
                }
            }
            // 记录 [0..i] 处理完后, 对 [0..i+1) 区间的分割信息
            left[i + 1][0] = num;
            left[i + 1][1] = mask;
            left[i + 1][2] = count;
        }
        
        // 计算右半部分信息 (从右到左遍历)
        num = 0, mask = 0, count = 0;
        for (int i = n - 1; i > 0; i--) {
            int binary = 1 << (s[i] - 'a');
            if (!(mask & binary)) {
                count++;
                if (count <= k) {
                    mask |= binary;
                } else {
                    num++;
                    mask = binary;
                    count = 1;
                }
            }
            // 记录 [i..n-1] 处理完后, 对 [i-1..n-1) 区间的分割信息
            right[i - 1][0] = num;
            right[i - 1][1] = mask;
            right[i - 1][2] = count;
        }
        
        int Max = 0;
        // 枚举每个可能的修改位置i
        for (int i = 0; i < n; i++) {
            // 基础分割数 = 左半部分分割数 + 右半部分分割数 + 1(当前字符所在块) + 1(修正偏移)
            int seg = left[i][0] + right[i][0] + 2;
            
            // 计算左半最后一块和右半第一块的合并字符集
            int totMask = left[i][1] | right[i][1];  // 合并掩码
            int totCount = 0;                        // 合并后的不同字符数
            while (totMask) {                        // 统计掩码中1的个数(即不同字符数)
                totMask &= totMask - 1;
                totCount++;
            }
            
            // 分析修改当前字符后的分割数变化
            if (left[i][2] == k && right[i][2] == k && totCount < 26) {
                // 情况1: 左右块均达k个字符, 且合并后仍有可替换字符, 修改后可增加一个分割
                seg++;
            } else if (min(totCount + 1, 26) <= k) {
                // 情况2: 合并后字符数(+1是因为当前字符可替换) <=k, 左右块可合并, 减少一个分割
                seg--;
            }
            
            Max = max(Max, seg);
        }
        return Max;
    }
};

// 法二
class Solution {
public:
    int maxPartitionsAfterOperations(string s, int k) {
        // 特殊情况：k=26时所有小写字母都能包含在一段，直接返回1
        if (k == 26) {
            return 1;
        }

        int seg = 1;    // 当前分割段数
        int mask = 0;   // 位掩码：记录当前段包含的字符（1<<字母偏移表示存在该字符）
        int size = 0;   // 当前段的不同字符数量
        //  lambda函数：更新当前分割状态（处理字符s[i]后调整段数、掩码、字符数）
        auto update = [&](int i) -> void {
            int bit = 1 << (s[i] - 'a');  // 当前字符对应的位
            if (mask & bit) {             // 字符已在当前段，无需调整
                return;
            }
            if (++size > k) {             // 新增字符后超出k个，需分割成新段
                seg++;
                mask = bit;               // 新段初始化为当前字符
                size = 1;
            } else {
                mask |= bit;              // 字符加入当前段
            }
        };

        int n = s.length();
        // 后缀数组：suf[i] = {seg, mask} 表示s[i..n-1]的分割段数和第一段的字符掩码
        vector<pair<int, int>> suf(n + 1);
        // 从右向左遍历，预处理后缀分割信息
        for (int i = n - 1; i >= 0; i--) {
            update(i);
            suf[i] = {seg, mask};
        }

        int ans = seg;  // 初始值：不修改任何字符的分割数
        // 重置状态，从左向右遍历，计算修改每个位置后的最大分割数
        seg = 1; mask = 0; size = 0;
        for (int i = 0; i < n; i++) {
            // 取s[i+1..n-1]的后缀信息：段数suf_seg、第一段掩码suf_mask
            auto [suf_seg, suf_mask] = suf[i + 1];
            // 情况3：默认分割数=左段(s[0..i])数 + 右段(s[i+1..n-1])数
            int res = seg + suf_seg;
            // 计算左段最后一段与右段第一段的合并字符数（位掩码OR后统计1的个数）
            int union_size = popcount((uint32_t)(mask | suf_mask));

            // 分析修改s[i]后的分割数变化
            if (union_size < k) {
                // 情况1：合并后字符数<k，修改s[i]可让左右段合并，分割数-1
                res--;
            } else if (union_size < 26 && size == k && popcount((uint32_t)suf_mask) == k) {
                // 情况2：合并后字符数<26（有可替换字符），且左右段原均满k个字符，修改后可多分割1次
                res++;
            }

            ans = max(ans, res);  // 更新最大分割数
            update(i);            // 将s[i]加入左段，更新左段状态
        }
        return ans;
    }
};

// 法三
class Solution {
public:
    int maxPartitionsAfterOperations(string s, int k) {
        if (k >= 26) return 1; // 所有字符可放一段，直接返回1

        int seg = 1;    // 当前分割段数
        int mask = 0;   // 位掩码：记录当前段字符（1<<字母偏移表示存在）
        int size = 0;   // 当前段不同字符数
        // 更新分割状态：处理字符s[i]后调整段数、掩码和字符数
        auto update = [&](char c) {
            int bit = 1 << (c - 'a');
            if (mask & bit) return; // 字符已在当前段，无需操作
            if (++size > k) {       // 超出k个不同字符，需新起一段
                seg++;
                mask = bit;
                size = 1;
            } else {
                mask |= bit;        // 加入当前段
            }
        };

        int n = s.size();
        // 后缀信息：suf[i] = {段数, 首段掩码} 表示s[i..n-1]的分割情况
        vector<pair<int, int>> suf(n + 1);
        // 从右向左预处理后缀
        seg = 1, mask = 0, size = 0; // 重置状态
        for (int i = n - 1; i >= 0; --i) {
            update(s[i]);
            suf[i] = {seg, mask};
        }

        int ans = suf[0].first; // 初始值：不修改字符的分割数
        // 从左向右计算修改每个位置的最大可能分割数
        seg = 1, mask = 0, size = 0; // 重置状态
        for (int i = 0; i < n; ++i) {
            auto [suf_seg, suf_mask] = suf[i + 1]; // 右段(s[i+1..n-1])信息
            int res = seg + suf_seg; // 基础分割数：左段+右段

            // 计算左右段合并后的字符数（位运算高效统计）
            int union_mask = mask | suf_mask;
            int union_size = __builtin_popcount(union_mask);

            // 分析修改s[i]后的影响
            if (union_size < k) {
                // 合并后字符数<k，修改后可合并左右段，分割数-1
                res--;
            } else if (union_size < 26 && size == k && __builtin_popcount(suf_mask) == k) {
                // 左右段原均满k个字符，且存在可替换字符，修改后可多分割1次
                res++;
            }

            ans = max(ans, res);
            update(s[i]); // 将当前字符加入左段
        }

        return ans;
    }
};